package com.company.algo.stack;

import java.util.HashMap;
import java.util.Stack;

/**
 * 最大频率栈
 push 和 pop 方法，难点如下：
 1、每次 pop 时，必须要知道频率最高的元素是什么。
 2、如果频率最高的元素有多个，还得知道哪个是最近 push 进来的元素是哪个。
 为了实现上述难点，我们要做到以下几点：
 1、肯定要有一个变量 maxFreq 记录当前栈中最高的频率是多少。
 2、我们得知道一个频率 freq 对应的元素有哪些，且这些元素要有时间顺序。
 3、随着 pop 的调用，每个 val 对应的频率会变化，所以还得维持一个映射记录每个 val 对应的 freq。
 */
public class FreqStack {
    // 记录 FreqStack 中元素的最大频率
    int maxFreq = 0;
    // 记录 FreqStack 中每个 val 对应的出现频率，后文就称为 VF 表
    HashMap<Integer, Integer> valToFreq = new HashMap<>();
    // 记录频率 freq 对应的 val 列表，后文就称为 FV 表
    HashMap<Integer, Stack<Integer>> freqToVals = new HashMap<>();

    // 在栈中加入一个元素 val
    public void push(int val) {
        //修改VF表：val对应的freq+1
        int freq = valToFreq.getOrDefault(val,0)+1;
        valToFreq.put(val,freq);
        //修改FV表：在freq对应的列表中加入val
        freqToVals.putIfAbsent(freq,new Stack<>());
        freqToVals.get(freq).push(val);
        //更新maxFreq
        maxFreq = Math.max(maxFreq,freq);
    }

    // 从栈中删除并返回出现频率最高的元素
    // 如果频率最高的元素不止一个，
    // 则返回最近添加的那个元素
    public int pop() {
        Stack<Integer> stack = freqToVals.get(maxFreq);
        int val = stack.pop();
        int freq = valToFreq.get(val) - 1;
        valToFreq.put(val,freq);
        if (stack.isEmpty()){
            maxFreq--;
        }
        return val;
    }
}
